package com.jxb.six;

/**
 * 单词搜索
 *  * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
 *  * 如果 word 存在于网格中，返回 true ；否则，返回 false 。
 *  * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，
 *  * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 *  * 同一个单元格内的字母不允许被重复使用。
 *
 * @author jiaobo
 * @date Created in 2025/1/4 17:44
 **/
public class WordSearch_79 {

    public static void main(String[] args) {
        char a = 'A';
        char c = a ^= 256;
        new WordSearch_79().exist(new char[][]{{'A','B','C','E'},
                {'S','F','C','S'},{'A','D','E','E'}},"ABCCED");
    }

    public boolean exist(char[][] board, String word) {
        char[] w = word.toCharArray();
        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y< board[x].length; y++) {
                if (backTrack(board,x,y,w,0)) return true;
            }
        }
        return false;
    }

    private boolean backTrack(char[][] board, int x, int y, char[] word, int currLength) {
        if (currLength == word.length) {
            return true;
        }
        //越界检查Ł
        if (x<0 || y<0 || x == board.length || y == board[x].length) return false;
        if (board[x][y] != word[currLength]) return false;
        //通过异或标识元素已经被访问过
        board[x][y] ^= 256;
        //按照右、下、左、上的顺序进行试探z
        boolean exist = backTrack(board,x,y+1,word,currLength+1)
                || backTrack(board,x-1,y,word,currLength+1)
                || backTrack(board,x+1,y,word,currLength+1)
                || backTrack(board,x,y-1,word,currLength+1);
        /*回溯，再次异或,复原原来的元素值*/
        board[x][y] ^= 256;
        return false;
    }

}
